package datastructure.linked;

/**
 * 双向环形链表-带哨兵
 *
 * @author 杨 强
 * @package datastructure.linked
 * @createTime 2023-03-12 16:48
 */
public class RingLinkedListSentinel {

    /**
     * 哨兵节点
     */
    private Node sentinelNode = new Node(null, -1, null);

    /**
     * 初始化双向环形链表
     */
    public RingLinkedListSentinel() {
        this.sentinelNode.next = this.sentinelNode;
        this.sentinelNode.prev = this.sentinelNode;
    }

    /**
     * 添加头部节点
     * @param value
     */
    public void addFirst(int value){
        // 头部节点
        Node a = sentinelNode;
        // 头部节点的下一个节点
        Node b = sentinelNode.next;
        // 创建新节点
        Node added = new Node(a,value,b);
        // 指针变化
        a.next = added;
        b.prev = added;
    }

    /**
     * 添加尾部节点
     * @param value
     */
    public void addLast(int value){
        // 得到头部节点的上一个节点
        Node a = sentinelNode.prev;
        // 头部节点
        Node b = sentinelNode;
        // 创建新节点
        Node added = new Node(a,value,b);
        // 指针变化
        a.next = added;
        b.prev = added;
    }

    /**
     * 删除第一个
     */
    public void removeFirst(){
        Node removed = sentinelNode.next;
        // 链表只剩哨兵本身就抛出异常
        if (removed == sentinelNode){
            throw new IllegalArgumentException("非法");
        }
        Node a = sentinelNode;
        // 指针变化
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个
     */
    public void removeLast() {
        Node removed = sentinelNode;
        if (removed == sentinelNode) {
            throw new IllegalArgumentException("非法");
        }
        Node a = removed.prev;
        Node b = sentinelNode;
        a.next = b;
        b.prev = a;
    }


    /**
     * 根据值删除节点
     * <p>假定 value 在链表中作为 key, 有唯一性</p>
     * @param value 待删除值
     */
    public void removeByValue(int value) {
        Node removed = findNodeByValue(value);
        if (removed != null) {
            Node prev = removed.prev;
            Node next = removed.next;
            prev.next = next;
            next.prev = prev;
        }
    }

    private Node findNodeByValue(int value) {
        Node p = sentinelNode.next;
        while (p != sentinelNode) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    /**
     * 节点类
     */
    private static class Node{
        // 上一个节点指针
        Node prev;
        // 值
        int value;
        // 下一个节点指针
        Node next;
        // 构造方法
        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}
